package com.fr.lintcode;

import java.util.Arrays;

public class Q818 {
    /**
     * @param nums:
     *            the array
     * @param target:
     *            the target
     * @return: the number of subsets which meet the following conditions
     */
    public long subsetWithTarget(int[] nums, int target) {
        // Write you code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        long sum = 0;
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            if (nums[l] + nums[r] < target) {
                sum += (1l << (r - l));
                l++;
            } else {
                r--;
            }
        }
        return sum;
    }
}
